// https://leetcode.cn/problems/palindrome-partitioning-ii/
// Created by ade on 2022/7/26.
// 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
//
// 返回符合要求的 最少分割次数 。
#include <iostream>
#include <vector>
#include <string>
#include <numeric>

using namespace std;

class Solution {
public:
    // 官方方法
    int minCut(string s) {
        int len = s.size();
        vector <vector<bool>> cache(len, vector<bool>(len, true));// 横坐标left 纵坐标right
        for (int i = len - 1; i >= 0; --i) {
            for (int j = i + 1; j < len; ++j) {
                cache[i][j] = (s[i] == s[j]) && cache[i + 1][j - 1];
            }
        }
        vector<int> dp(len);
        iota(dp.begin(), dp.end(), 0);
        for (int i = 1; i < len; i++) {
            if (cache[0][i]) {
                dp[i] = 0;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if (cache[j + 1][i]) {
                    dp[i] = min(dp[j] + 1, dp[i]);
                }
            }
        }

        return dp[len - 1];
    }

//    bool isPalindrom(const string &s, int left, int right) {
////        if (left == right || left == right - 1) {
////            if (s[left] == s[right]) {
////                cache[left][right] = 1;
////                return true;
////            } else {
////                cache[left][right] = -1;
////                return false;
////            }
////        }
////        if (s[left] == s[right] && isPalindrom(s, left + 1, right - 1)) {
////            cache[left][right] = 1;
////            return true;
////        } else {
////            cache[left][right] = -1;
////            return false;
////        }
//        while (left < right) {
//            if (s[left] != s[right]) return false;
//            left++;
//            right--;
//        }
//        return true;
//    }
};

int main() {
//    string s = "ababababababababababababcbabababababababababababa";
    string s = "cdd";
    Solution so;
    int a = so.minCut(s);
    cout << a << endl;
    return 0;
}